{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Anagrams in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findAnagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到字符串中所有字母异位词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串&nbsp;<code>s</code>&nbsp;和 <code>p</code>，找到&nbsp;<code>s</code><strong>&nbsp;</strong>中所有&nbsp;<code>p</code><strong>&nbsp;</strong>的&nbsp;<strong>异位词&nbsp;</strong>的子串，返回这些子串的起始索引。不考虑答案输出的顺序。</p>\n",
    "\n",
    "<p><strong>异位词 </strong>指由相同字母重排列形成的字符串（包括相同的字符串）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"cbaebabacd\", p = \"abc\"\n",
    "<strong>输出: </strong>[0,6]\n",
    "<strong>解释:</strong>\n",
    "起始索引等于 0 的子串是 \"cba\", 它是 \"abc\" 的异位词。\n",
    "起始索引等于 6 的子串是 \"bac\", 它是 \"abc\" 的异位词。\n",
    "</pre>\n",
    "\n",
    "<p><strong>&nbsp;示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"abab\", p = \"ab\"\n",
    "<strong>输出: </strong>[0,1,2]\n",
    "<strong>解释:</strong>\n",
    "起始索引等于 0 的子串是 \"ab\", 它是 \"ab\" 的异位词。\n",
    "起始索引等于 1 的子串是 \"ba\", 它是 \"ab\" 的异位词。\n",
    "起始索引等于 2 的子串是 \"ab\", 它是 \"ab\" 的异位词。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, p.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;和&nbsp;<code>p</code>&nbsp;仅包含小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-anagrams-in-a-string](https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-anagrams-in-a-string](https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cbaebabacd\"\\n\"abc\"', '\"abab\"\\n\"ab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        if len(s) == 0 or len(s) < len(p): return []\n",
    "        res = []\n",
    "        # p = sorted(p)\n",
    "        # for i in range(0, len(s)-len(p)+1):\n",
    "        #     if s[i] not in p: continue\n",
    "        #     curr_sub = s[i:i+len(p)]\n",
    "        #     if sorted(curr_sub) == p:\n",
    "        #         res.append(i)\n",
    "        # return res\n",
    "        \n",
    "        # although the above method works, but it is too slow.\n",
    "        p_count = Counter(p)\n",
    "        s_count = Counter()\n",
    "        \n",
    "        ns, np = len(s), len(p)\n",
    "        # sliding window on the string s\n",
    "        for i in range(ns):\n",
    "            # add one more letter \n",
    "            # on the right side of the window\n",
    "            s_count[s[i]] += 1\n",
    "            # remove one letter \n",
    "            # from the left side of the window\n",
    "            if i >= np:\n",
    "                if s_count[s[i-np]] == 1:\n",
    "                    del s_count[s[i-np]]\n",
    "                else:\n",
    "                    s_count[s[i-np]] -= 1\n",
    "            # compare array in the sliding window\n",
    "            # with the reference array\n",
    "            if p_count == s_count:\n",
    "                res.append(i-np+1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # Solution 1: 使用两个1*26大小的dict字典，通过窗口滑动的思想判断是否有符合条件的连续子串可以在字符串s当中\n",
    "        # DP\n",
    "    \n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        Dict = defaultdict(int)\n",
    "        for i in range(26):\n",
    "            Dict[chr(ord('a') + i)] = i\n",
    "        \n",
    "        pfind = [0] * 26\n",
    "        \n",
    "        for i in p:\n",
    "            pfind[Dict[i]] += 1\n",
    "        \n",
    "        sfind = [0] * 26\n",
    "        \n",
    "        np = len(p)\n",
    "        ns = len(s)\n",
    "        \n",
    "        result = []\n",
    "        for i in range(np):\n",
    "            sfind[Dict[s[i]]] += 1\n",
    "            if sfind == pfind:\n",
    "                result.append(0)\n",
    "        \n",
    "        for i in range(1, ns - np + 1):\n",
    "            sfind[Dict[s[i - 1]]] -= 1\n",
    "            sfind[Dict[s[i + np - 1]]] += 1\n",
    "            if sfind == pfind:\n",
    "                result.append(i)\n",
    "                \n",
    "        return result\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not s or len(s) < len(p):\n",
    "            return []\n",
    "        ls, lp = len(s), len(p)\n",
    "        count = lp\n",
    "        cp = collections.Counter(p)\n",
    "        cs = collections.Counter()\n",
    "        ans = []\n",
    "        for i in range(ls):\n",
    "            cs[s[i]] += 1\n",
    "            if i >= lp:\n",
    "                cs[s[i - lp]] -= 1\n",
    "                if cs[s[i-lp]] == 0:\n",
    "                    del cs[s[i-lp]]\n",
    "            if cs == cp:\n",
    "                ans.append(i-lp+1)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        # target = self.convert(p)\n",
    "        # for index in range(0, len(s) - len(p) + 1):\n",
    "        #     if self.convert(s[index:index+len(p)]) == target:\n",
    "        #         res.append(index)\n",
    "        # return res\n",
    "    # def convert(self, s):\n",
    "    #     temp = {}\n",
    "    #     for x in s:\n",
    "    #         if x not in temp:\n",
    "    #             temp[x] = 1\n",
    "    #         else:\n",
    "    #             temp[x] += 1\n",
    "    #     return temp\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not p: return []\n",
    "        def isAnagram(s, t):\n",
    "            for i in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if s.count(i) != t.count(i):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        res = []\n",
    "        length = len(p)\n",
    "        for i in range(len(s)):\n",
    "            if i + length <= len(s) and isAnagram(s[i: i + length], p):\n",
    "                res.append(i)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: 'str', p: 'str') -> 'List[int]':\n",
    "        res = []\n",
    "        pCounter = collections.Counter(p)\n",
    "        sCounter = collections.Counter(s[:len(p)-1])\n",
    "        for i in range(len(p)-1,len(s)):\n",
    "            sCounter[s[i]] += 1\n",
    "            if sCounter == pCounter:\n",
    "                res.append(i-len(p)+1)\n",
    "            sCounter[s[i-len(p)+1]] -= 1\n",
    "            if sCounter[s[i-len(p)+1]] == 0:\n",
    "                del sCounter[s[i-len(p)+1]]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ls = list(s)\n",
    "        lp = list(p)\n",
    "        a = []\n",
    "        for i in range(len(s)-len(p)+1):\n",
    "            if set(ls[i:i+len(p)])==set(lp):\n",
    "                d1=dict(Counter(ls[i:i+len(p)]))\n",
    "                d2=dict(Counter(lp))\n",
    "                if len([i for i in d1 if d1[i]==d2[i]])==len(d1):\n",
    "                    a.append(i)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        base = ord(\"a\")\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        window = {k : 0 for k in range(26)}\n",
    "        lengthA = len(p)\n",
    "        for item in p :\n",
    "            window[ord(item) - base] -= 1\n",
    "        for indx in range(lengthA):\n",
    "            window[ord(s[indx]) - base] += 1\n",
    "        if all([k == 0 for k in window.values()]):\n",
    "            ans.append(0)\n",
    "        for indx in range(lengthA, len(s)):\n",
    "            window[ord(s[indx - lengthA]) - base] -= 1\n",
    "            window[ord(s[indx]) - base] += 1\n",
    "            if all([k == 0 for k in window.values()]):\n",
    "                ans.append(indx - lengthA + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(s)<len(p):\n",
    "            return []\n",
    "        flag={}\n",
    "        for i in p:\n",
    "            if i not in flag:\n",
    "                flag[i]=1\n",
    "            else:\n",
    "                flag[i]+=1\n",
    "        unin={}\n",
    "        for i in s[:len(p)]:\n",
    "            if i not in flag or flag[i]==0:\n",
    "                if i not in unin:\n",
    "                    unin[i]=1\n",
    "                else:\n",
    "                    unin[i]+=1\n",
    "            else:\n",
    "                flag[i]-=1\n",
    "        zuo=0\n",
    "        you=len(p)\n",
    "        ans=[]\n",
    "        while you<len(s):\n",
    "            if not unin:\n",
    "                ans.append(zuo)\n",
    "            if s[zuo] in unin:\n",
    "                unin[s[zuo]]-=1\n",
    "                if unin[s[zuo]]==0:\n",
    "                    unin.pop(s[zuo])\n",
    "            else:\n",
    "                flag[s[zuo]]+=1\n",
    "\n",
    "            if s[you] not in flag or flag[s[you]]==0:\n",
    "                if s[you] not in unin:\n",
    "                    unin[s[you]]=1\n",
    "                else:\n",
    "                    unin[s[you]]+=1\n",
    "            else:\n",
    "                flag[s[you]]-=1\n",
    "            zuo+=1\n",
    "            you+=1\n",
    "        else:\n",
    "            if not unin:\n",
    "                ans.append(zuo)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import defaultdict\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # Solution 1: 使用两个1*26大小的dict字典，通过窗口滑动的思想判断是否有符合条件的连续子串可以在字符串s当中\n",
    "        # DP\n",
    "    \n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "        \n",
    "        Dict = {}\n",
    "        for i in range(26):\n",
    "            Dict[chr(ord('a') + i)] = i\n",
    "        \n",
    "        pfind = [0] * 26\n",
    "        \n",
    "        for i in p:\n",
    "            pfind[Dict[i]] += 1\n",
    "        \n",
    "        sfind = [0] * 26\n",
    "        \n",
    "        np = len(p)\n",
    "        ns = len(s)\n",
    "        \n",
    "        result = []\n",
    "        for i in range(np):\n",
    "            sfind[Dict[s[i]]] += 1\n",
    "            if sfind == pfind:\n",
    "                result.append(0)\n",
    "        \n",
    "        for i in range(1, ns - np + 1):\n",
    "            sfind[Dict[s[i - 1]]] -= 1\n",
    "            sfind[Dict[s[i + np - 1]]] += 1\n",
    "            if sfind == pfind:\n",
    "                result.append(i)\n",
    "                \n",
    "        return result\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        slide = len(p)\n",
    "        \n",
    "        # 字符集合\n",
    "        cpk = set(p)\n",
    "        # 哈希表计数\n",
    "        pk ={}\n",
    "        for i in p:\n",
    "            if i in pk:\n",
    "                pk[i]+=1\n",
    "            else:\n",
    "                pk[i]=1\n",
    "            \n",
    "        for i in range(len(s)-slide+1):\n",
    "            if set(s[i:i+slide])!=cpk:\n",
    "                continue\n",
    "                \n",
    "            dk ={}\n",
    "            for j in s[i:i+slide]:\n",
    "                if j in dk:\n",
    "                    dk[j]+=1\n",
    "                else:\n",
    "                    dk[j]=1\n",
    "            \n",
    "            if dk == pk:\n",
    "                res.append(i)\n",
    "        return res\n",
    "                \n",
    "             \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        slide = len(p)\n",
    "        nums = [ord(i) for i in s]\n",
    "        p_sum = sum([ord(i) for i in p])\n",
    "        \n",
    "        res = []\n",
    "        # 字符集合\n",
    "        cpk = set(p)\n",
    "            \n",
    "        for i in range(len(s)-slide+1):\n",
    "            if set(s[i:i+slide])!=cpk:\n",
    "                continue\n",
    "            elif sum(nums[i:i+slide])!=p_sum:\n",
    "                continue\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return res\n",
    "                \n",
    "             \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        if s_len<p_len or s_len*p_len==0:\n",
    "            return []\n",
    "        record = {}\n",
    "        for i in range(p_len):\n",
    "            record[p[i]] = record.get(p[i],0) + 1\n",
    "        count = p_len\n",
    "        left = right = 0\n",
    "        res = []\n",
    "        while right < s_len:\n",
    "            if s[right] in record:\n",
    "                if record[s[right]]>=1:\n",
    "                    count -= 1\n",
    "                record[s[right]] -= 1\n",
    "            right += 1\n",
    "            if count == 0:\n",
    "                res.append(left)\n",
    "            if right-left == p_len:\n",
    "                if s[left] in record:\n",
    "                    if record[s[left]] >= 0:\n",
    "                        count += 1\n",
    "                    record[s[left]] += 1\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return []\n",
    "        res = []\n",
    "        for i in range(0,len(s)+1-len(p)):\n",
    "            if set(s[i:i+len(p)]) == set(p):\n",
    "                if all (s[i:i+len(p)].count(j) == p.count(j) for j in sorted(set(p))):\n",
    "                    res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_count = [0]*26\n",
    "        w_count = [0]*26\n",
    "        k = ord('a')\n",
    "        for i in p:\n",
    "            s_count[ord(i)-k] += 1\n",
    "        res = []\n",
    "        match,left,right = 0,0,0\n",
    "        while(left<len(s)):\n",
    "            if s[left] in p:\n",
    "                w_count[ord(s[left])-k] += 1\n",
    "                if w_count[ord(s[left])-k] <= s_count[ord(s[left])-k]:\n",
    "                    match += 1\n",
    "            left += 1\n",
    "            while(match == len(p)):\n",
    "                if left - right == len(p):\n",
    "                    res.append(right)\n",
    "                if s[right] in p:\n",
    "                    w_count[ord(s[right])-k] -= 1\n",
    "                    if w_count[ord(s[right])-k] < s_count[ord(s[right])-k]:\n",
    "                        match -= 1\n",
    "                right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams2(self, s: str, p: str):\n",
    "        if s is None or len(s) == 0 or len(s) < len(p):\n",
    "            return []\n",
    "        from collections import Counter\n",
    "        needs = Counter(p)\n",
    "        len_p, len_s = len(p), len(s)\n",
    "        res = []\n",
    "        for i in range(len_s-len_p+1):\n",
    "            current = Counter()\n",
    "            match = 0\n",
    "            for j in range(i, i+len_p):\n",
    "                w = s[j]\n",
    "                if w in needs:\n",
    "                    current[w] += 1\n",
    "                    if current[w] > needs[w]:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "                match += 1\n",
    "            if match == len_p:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "    def findAnagrams(self, s: str, p: str):\n",
    "        if s is None or len(s) == 0 or len(s) < len(p):\n",
    "            return []\n",
    "        from collections import Counter\n",
    "        needs = Counter(p)\n",
    "        left, right, match = 0, 0, 0\n",
    "        windows = Counter()\n",
    "        res = []\n",
    "        while right < len(s):\n",
    "            if s[right] in needs:\n",
    "                windows[s[right]] += 1\n",
    "                if windows[s[right]] == needs[s[right]]:\n",
    "                    match += 1\n",
    "            right += 1\n",
    "            # 窗口满足要求了\n",
    "            while match == len(needs):\n",
    "                if right - left == len(p):\n",
    "                    res.append(left)\n",
    "                if s[left] in needs:\n",
    "                    windows[s[left]] -= 1\n",
    "                    if windows[s[left]] < needs[s[left]]:\n",
    "                        match -= 1\n",
    "                left += 1\n",
    "        return res\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = \"baa\"\n",
    "    p = \"aa\"\n",
    "    solution = Solution()\n",
    "    print(solution.findAnagrams(s, p))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "    def findAnagrams(self, s: str, p: str) -> list:\n",
    "        if len(s) < len(p):\n",
    "            return []\n",
    "\n",
    "        hash = [0] * 26\n",
    "        l, count, res = 0, 0, []\n",
    "\n",
    "        for idx in range(len(p)):\n",
    "            hash[ord(p[idx]) - ord('a')] += 1\n",
    "\n",
    "        for r in range(len(s)):\n",
    "            hash[ord(s[r]) - ord('a')] -= 1\n",
    "            if hash[ord(s[r]) - ord('a')] >= 0:\n",
    "                count += 1\n",
    "            if r > len(p) - 1:\n",
    "                hash[ord(s[l]) - ord('a')] += 1\n",
    "                if hash[ord(s[l]) - ord('a')] > 0:\n",
    "                    count -= 1\n",
    "\n",
    "                l += 1\n",
    "\n",
    "            if count == len(p):\n",
    "                res.append(l)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\r\n",
    "        length = len(p)\r\n",
    "        target = self.stringArray(p)\r\n",
    "        result = list()\r\n",
    "        current = None\r\n",
    "        for i in range(len(s) - length + 1):\r\n",
    "            if i == 0:\r\n",
    "                current = self.stringArray(s[i : i + length])\r\n",
    "            else:\r\n",
    "                current[ord(s[i - 1]) - ord('a')] -= 1\r\n",
    "                current[ord(s[i + length - 1]) - ord('a')] += 1\r\n",
    "            if current == target:\r\n",
    "                result.append(i)\r\n",
    "        return result\r\n",
    "    \r\n",
    "    def stringArray(self, s):\r\n",
    "        result = [0] * 26\r\n",
    "        for x in s:\r\n",
    "            result[ord(x) - ord('a')] += 1\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ord_a = ord('a')\n",
    "def counter(s):\n",
    "    return [s.count(c) for c in string.ascii_lowercase]\n",
    "\n",
    "class Solution(object):\n",
    "    def findAnagrams(self, s, p):\n",
    "        counts = counter(s[:len(p)])\n",
    "        target = counter(p)\n",
    "        if counts == target:\n",
    "            yield 0\n",
    "        for i, c in enumerate(s[len(p):]):\n",
    "            counts[ord(s[i])-ord_a] -= 1\n",
    "            counts[ord(c)-ord_a] += 1\n",
    "            if counts == target:\n",
    "                yield i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        # 滑动窗口\n",
    "        # need,window = collections.defaultdict(int),collections.defaultdict(int)\n",
    "        # for c in p:\n",
    "        #     need[c] += 1\n",
    "        # left,right = 0,0\n",
    "        # res,valid = [],0\n",
    "        # while right < len(s):\n",
    "        #     c = s[right]\n",
    "        #     right += 1\n",
    "        #     if c in need:\n",
    "        #         window[c] += 1\n",
    "        #         if window[c] == need[c]:\n",
    "        #             valid += 1\n",
    "        #     while valid == len(need):\n",
    "        #         if right - left == len(p):\n",
    "        #             res.append(left)\n",
    "        #         d = s[left]\n",
    "        #         left += 1\n",
    "        #         if d in need:\n",
    "        #             if window[d] == need[d]:\n",
    "        #                 valid -= 1\n",
    "        #             window[d] -= 1\n",
    "        # return res\n",
    "\n",
    "        need,window = collections.defaultdict(int),collections.defaultdict(int)\n",
    "        for c in p:\n",
    "            need[c] += 1\n",
    "        valid = 0 \n",
    "        left,right = 0,0\n",
    "        res = []\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            while valid == len(need):\n",
    "                if right - left == len(p):\n",
    "                    res.append(left)\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "        return res\n",
    "\n",
    "        # need,window = collections.defaultdict(int),collections.defaultdict(int)\n",
    "        # for c in p:\n",
    "        #     need[c] += 1\n",
    "        # left,right = 0,0\n",
    "        # res,valid = [],0\n",
    "        # while right < len(s):\n",
    "        #     c = s[right]\n",
    "        #     right += 1\n",
    "        #     if c in need:\n",
    "        #         window[c] += 1\n",
    "        #         if window[c] == need[c]:\n",
    "        #             valid += 1\n",
    "        #     while right - left >= len(p):\n",
    "        #         if valid == len(need):\n",
    "        #             res.append(left)\n",
    "        #         d = s[left]\n",
    "        #         left += 1\n",
    "        #         if d in need:\n",
    "        #             if window[d] == need[d]:\n",
    "        #                 valid -= 1\n",
    "        #             window[d] -= 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        len1 = len(s)\n",
    "        len2 = len(p)\n",
    "        if len2 >= len1:\n",
    "            return []\n",
    "\n",
    "        def stringtoDict(s):\n",
    "            stringDict = {}\n",
    "            for c in s:\n",
    "                if c not in stringDict:\n",
    "                    stringDict[c] = 1\n",
    "                else:\n",
    "                    stringDict[c] += 1\n",
    "            return stringDict\n",
    "        \n",
    "        ans = []\n",
    "        target_dict = stringtoDict(p)\n",
    "        object_dict = stringtoDict(s[:len2])\n",
    "        for idx in range(len1-len2+1):\n",
    "                if self.isAnagrams(object_dict, target_dict):\n",
    "                    ans.append(idx)\n",
    "                # update object_dict\n",
    "                object_dict[s[idx]] -= 1\n",
    "                if object_dict[s[idx]] == 0:\n",
    "                    object_dict.pop(s[idx])\n",
    "                if idx+len2 < len1:\n",
    "                    c = s[idx+len2]\n",
    "                    if c not in object_dict:\n",
    "                        object_dict[c] =1\n",
    "                    else:\n",
    "                        object_dict[c] += 1\n",
    "\n",
    "        return ans\n",
    "        \n",
    "    def isAnagrams(self, d1: dict, d2: dict) -> bool:\n",
    "        if set(d1.keys()) != set(d2.keys()):\n",
    "            return False\n",
    "\n",
    "        for key in d1:\n",
    "            if key in d2 and d1[key] != d2[key]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        p_len = len(p)\n",
    "        p_format = list(p)\n",
    "        p_format.sort()\n",
    "        res = []\n",
    "        for i in range(len(s) - p_len + 1):\n",
    "            temp = list(s[i: i + p_len])\n",
    "            temp.sort()\n",
    "            if temp == p_format:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        res=[]\n",
    "        char_dic={}\n",
    "        need=len(p)\n",
    "        for item in p:\n",
    "            if item not in char_dic:\n",
    "                char_dic[item]=0\n",
    "            char_dic[item]+=1\n",
    "        start=0\n",
    "        end=start\n",
    "        while end<n:\n",
    "            if s[end] in char_dic:\n",
    "                char_dic[s[end]]-=1\n",
    "                if char_dic[s[end]]>=0:    \n",
    "                    need-=1\n",
    "            while end-start+1==len(p):\n",
    "                if need==0:\n",
    "                    res.append(start)\n",
    "                if s[start] in char_dic:\n",
    "                    char_dic[s[start]]+=1\n",
    "                    if char_dic[s[start]]>0:\n",
    "                        need+=1\n",
    "                start+=1\n",
    "            end+=1\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        needs = [0]*26\n",
    "        result = []\n",
    "        for i in range(len(p)):\n",
    "            needs[ord(p[i])-ord('a')] +=1\n",
    "        windows = [0]*26\n",
    "\n",
    "        left,right = 0,0\n",
    "\n",
    "        while right < len(s):\n",
    "            ch = ord(s[right])-ord('a')\n",
    "            windows[ch]+=1\n",
    "            right+=1\n",
    "\n",
    "\n",
    "            while windows[ch] > needs[ch]:\n",
    "                ch2 = ord(s[left]) - ord('a')\n",
    "                windows[ch2]-=1\n",
    "                left+=1\n",
    "            \n",
    "            if right - left == len(p):\n",
    "                result.append(left)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        s_len, p_len = len(s), len(p)\n",
    "        if s_len < p_len:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        s_count = [0] * 26\n",
    "        p_count = [0] * 26\n",
    "        for i in range(p_len):\n",
    "            s_count[ord(s[i]) - ord('a')] += 1\n",
    "            p_count[ord(p[i]) - ord('a')] += 1\n",
    "\n",
    "        if s_count == p_count:\n",
    "            ans.append(0)\n",
    "        for i in range(s_len - p_len):\n",
    "            s_count[ord(s[i]) - ord('a')] -= 1\n",
    "            s_count[ord(s[i + p_len]) - ord('a')] += 1\n",
    "\n",
    "            if s_count == p_count:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        windows, need = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        for c in p:\n",
    "            need[c] += 1\n",
    "        left, right = 0, 0\n",
    "        valid, res = 0, []\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1 \n",
    "            if c in need:\n",
    "                windows[c] += 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1     \n",
    "            while right - left >= len(p):\n",
    "                if valid == len(need):\n",
    "                    res.append(left)\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n,m = len(s), len(p)\n",
    "        scount = [0]*26\n",
    "        pcount = [0]*26\n",
    "        re = []\n",
    "        if n<m:\n",
    "            return []\n",
    "\n",
    "        for i in range(m):\n",
    "            scount[ord(s[i]) - 97] +=1\n",
    "            pcount[ord(p[i]) - 97] +=1\n",
    "        if scount == pcount:\n",
    "            re.append(0)\n",
    "        for i in range(n-m):\n",
    "           scount[ord(s[i]) - 97] -= 1\n",
    "           scount[ord(s[i+m]) - 97] += 1\n",
    "           if scount == pcount:\n",
    "               # print(f\"scount: {scount}\")\n",
    "               re.append(i+1)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        dic = {}\n",
    "        cmp = {}\n",
    "        n, m = len(s), len(p)\n",
    "        if n < m:\n",
    "            return []\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            dic[p[i]] = dic.get(p[i], 0)+1\n",
    "            cmp[s[i]] = cmp.get(s[i], 0)+1\n",
    "        for i in range(m, n):\n",
    "            # print(cmp)\n",
    "            if dic == cmp:\n",
    "                ans.append(i-m)\n",
    "            if s[i] == s[i-m]:\n",
    "                continue\n",
    "            else:\n",
    "                if cmp.get(s[i-m],0) > 1:\n",
    "                    cmp[s[i-m]] -= 1\n",
    "                else:\n",
    "                    del cmp[s[i-m]]\n",
    "                cmp[s[i]] = cmp.get(s[i], 0)+1\n",
    "                continue\n",
    "        \n",
    "        if dic == cmp:\n",
    "            ans.append(n-m)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        left, right, valid = 0, 0, 0\n",
    "        needs, window = {}, {}\n",
    "        ret = set()\n",
    "        for c in p:\n",
    "            if c in needs:\n",
    "                needs[c] += 1\n",
    "            else:\n",
    "                needs[c] = 1\n",
    "            window[c] = 0\n",
    "\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in needs:\n",
    "                window[c] += 1\n",
    "                if window[c] == needs[c]:\n",
    "                    valid += 1\n",
    "\n",
    "            while right - left >= len(p):\n",
    "                if valid == len(needs.keys()):\n",
    "                    ret.add(left)\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in needs:\n",
    "                    if window[d] == needs[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        n, m, l = len(s), len(p), []\n",
    "        if n < m:\n",
    "            return l\n",
    "        p_a = [0]*26\n",
    "        s_a = [0]*26\n",
    "        for i in range(m):\n",
    "            p_a[ord(p[i]) - ord('a')] += 1\n",
    "            s_a[ord(s[i]) - ord('a')] += 1\n",
    "        if s_a == p_a:\n",
    "            l.append(0)\n",
    "        for i in range(m, n):\n",
    "            s_a[ord(s[i]) - ord('a')] += 1\n",
    "            s_a[ord(s[i-m]) - ord('a')] -= 1\n",
    "            if s_a == p_a:\n",
    "                l.append(i-m+1)\n",
    "        return l\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        p_len = len(p)\n",
    "        s_len = len(s)\n",
    "        res = []\n",
    "\n",
    "        p_cnt = [0] * 26\n",
    "        s_cnt = [0] * 26\n",
    "\n",
    "        # 统计26个字母出现的次数\n",
    "        for i in range(p_len):\n",
    "            p_cnt[ord(p[i]) - ord('a')] += 1\n",
    "\n",
    "        start = 0\n",
    "        for end in range(s_len):\n",
    "            cur_end = ord(s[end]) - ord('a')\n",
    "            s_cnt[cur_end] += 1\n",
    "            while s_cnt[cur_end] > p_cnt[cur_end]:\n",
    "                cur_start = ord(s[start]) - ord('a')\n",
    "                s_cnt[cur_start] -= 1\n",
    "                start += 1\n",
    "            if end - start + 1 == p_len:\n",
    "                res.append(start)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAnagrams(self, s: str, p: str) -> List[int]:\n",
    "        r = []\n",
    "        p = ''.join(sorted(p))\n",
    "        for i in range(len(s)-len(p)+1):\n",
    "            if ''.join(sorted(s[i:(i+len(p))])) == p:\n",
    "                r.append(i)\n",
    "        \n",
    "        return r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
